﻿#include <iostream>
using namespace std;

#include <set>
#include <map>
#include <string>


//前K个高频单词
//https://leetcode.cn/problems/top-k-frequent-words/submissions/
//排序解法
//class Solution {
//public:
//    struct Compare
//    {
//        bool operator()(const pair<int, string>& p1, const pair<int, string>& p2)
//        {
//            return (p1.first > p2.first)
//                || (p1.first == p2.first && p1.second < p2.second);
//        }
//    };
//
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        map<string, int> m;
//        for (const auto& s : words) { ++m[s]; }
//        vector<pair<int, string>> v;
//        for (const auto& x : m)
//        {
//            v.push_back(make_pair(x.second, x.first));
//        }
//        stable_sort(v.begin(), v.end(), Compare());
//
//        vector<string> str;
//        for (int i = 0; i < k; ++i)
//        {
//            str.push_back(v[i].second);
//        }
//        return str;
//    }
//};
//删除法
//class Solution {
//public:
//    struct Compare
//    {
//        bool operator()(const pair<int, string>& p1, const pair<int, string>& p2)
//        {
//            return (p1.first > p2.first)
//                || (p1.first == p2.first && p1.second < p2.second);
//        }
//    };
//
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        map<string, int> m;
//        for (const auto& s : words) { ++m[s]; }
//        vector<pair<int, string>> v;
//        for (const auto& x : m)
//        {
//            v.push_back(make_pair(x.second, x.first));
//        }
//        stable_sort(v.begin(), v.end(), Compare());
//
//        vector<string> str;
//        for (int i = 0; i < k; ++i)
//        {
//            str.push_back(v[i].second);
//        }
//        return str;
//    }
//};


//两个数组的交集
//https://leetcode.cn/problems/intersection-of-two-arrays/
// 标记法
//class Solution {
//public:
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//        map<int, int> m;
//        vector<int> v;
//        for (const auto& n : nums1)
//        {
//            m[n] = 1;
//        }
//        for (const auto& n : nums2)
//        {
//            if (m[n] == 1)
//            {
//                v.push_back(n);
//                m[n] = 0;
//            }
//        }
//        return v;
//    }
//};
//排序去重法
//class Solution {
//public:
//
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//        set<int> s1(nums1.begin(), nums1.end());
//        set<int> s2(nums2.begin(), nums2.end());
//
//        vector<int> v;
//        auto it1 = s1.begin();
//        auto it2 = s2.begin();
//
//        while (it1 != s1.end() && it2 != s2.end())
//        {
//            if (*it1 == *it2)
//            {
//                v.push_back(*it1);
//                ++it1;
//                ++it2;
//            }
//            else if (*it1 > *it2)
//            {
//                ++it2;
//            }
//            else if (*it1 < *it2)
//            {
//                ++it1;
//            }
//        }
//        return v;
//    }
//};